package practise.alogrithm.introductionToAlogrithm.dataStructures;

import practise.alogrithm.introductionToAlogrithm.TreeBuilder;
import practise.alogrithm.introductionToAlogrithm.TreeNode;

import java.util.HashMap;

/**
 * Created by Richard on 7/21/2014.
 */
public class BinTreeSearch {

    /**
     * todo use the parent link for searching a tree, which is without extra space and nonrecursive
     */

    /**
     * this is a most simple in order in a recursive manner
     * @param root
     */
    public void inorder(TreeNode<Integer> root){
        if(root==null){
            return;
        }
        inorder(root.getLeft());
        System.out.print("["+root.getValue()+"]");
        inorder(root.getRight());
    }

    /**
     * as we use a width first method in loop manner in TreeBuilder, so there we use a recursive one
     * note the recursive method is not a width method
     * @param root
     * @return the previous level
     */
    public Integer searchTreeInRecursive(TreeNode<Integer> root){
        if(root==null){
            return 0;
        }

        if(root.getRight()==null && root.getLeft()==null){
            System.out.print("level:" + 1 + "[" + root.getValue()+"]");
            return 1;
        }

        Integer level = Math.max(searchTreeInRecursive(root.getLeft()),searchTreeInRecursive(root.getRight()))+1;
        System.out.print("level:" + level + "[" + root.getValue() + "]");
        return level;

    }

    public static void main(String[] args){
        TreeNode<Integer> root = TreeBuilder.createTreeByArrayInWidth(new Integer[]{1,2,3,4,5,6,7,8});
        TreeBuilder.printTreeInWidth(root);
        BinTreeSearch binTreeSearch = new BinTreeSearch();
        binTreeSearch.searchTreeInRecursive(root);
        System.out.println();
        System.out.println("In order");
        binTreeSearch.inorder(root);
    }

}
